package InterviewTest.q1709_getKthMagicNumber;

public class Solution_2 {
    /*
    更简单的方法是动态规划
    维护三个指针
    每次对应的三个位置乘以 3 5 7 然后查看哪个数字是此时的最小值 dp记录最小值后
    找出对应的指针 然后指针后移
    例如 3 5 7 找出最小值为3 那么此时p3后移 记录dp是3 下一次就是5 7 9
    此时p5后移 记录dp也就是5 符合数字变化的规律
     */
    public int getKthMagicNumber(int k) {
        int[] dp = new int[k + 1];
        dp[1] = 1;
        int p3 = 1, p5 = 1, p7 = 1;
        for (int i = 2; i <= k; i++) {
            int num3 = dp[p3] * 3, num5 = dp[p5] * 5, num7 = dp[p7] * 7;
            dp[i] = Math.min(Math.min(num3, num5), num7);
            if (dp[i] == num3) ++p3;
            if (dp[i] == num5) ++p5;
            if (dp[i] == num7) ++p7;
        }
        return dp[k];
    }
}
